
// 方案三
// 时间复杂度：O(n)
// 空间复杂度：O(n)
char* convert(char* s, int numRows) {
    if (numRows == 1) {
        return s;
    }

    char* res = (char*) malloc(sizeof(char) * (strlen(s) + 1));
    memset(res, '\0', sizeof(char) * (strlen(s) + 1)); // 初始化为 "\0"
    int delta = 2 * numRows - 2;
    int n = strlen(s);
    int index = 0;

    for (int row = 0; row < numRows; row++) {
        for (int col = 0; col + row < n; col += delta) {
            res[index] = s[col + row];
            index++;
            if (row != 0 && row != numRows - 1 && col + delta - row < n) {
                res[index] = s[col + delta - row];
                index++;
            }
        }
    }

    return res;
}

// 方案二
// 时间复杂度：O(n)
// 空间复杂度：O(n)
char* convert2(char* s, int numRows) {
    if (numRows == 1) {
        return s;
    }

    // 创建 numRows 个 StringBuilder
    char** sbs = (char**) malloc(sizeof(char*) * numRows);
    for (int i = 0; i < numRows; i++) {
        sbs[i] = (char*) malloc(sizeof(char) * (strlen(s) + 1)); // 预分配存储空间
        memset(sbs[i], '\0', sizeof(char) * (strlen(s) + 1)); // 初始化为 "\0"
    }

    int currRow = 0;
    bool goingDown = false;
    int n = strlen(s);

    for (int i = 0; i < n; i++) {
        sbs[currRow][strlen(sbs[currRow])] = s[i];

        if (currRow == 0 || currRow == numRows - 1) {
            goingDown = !goingDown;
        }
        currRow+= (goingDown ? 1 : -1);
    }

    char* res = (char*) malloc(sizeof(char) * (n + 1));
    memset(res, '\0', sizeof(char) * (n + 1)); // 初始化为 "\0"
    for (int j = 0; j < numRows; j++) {
        strcat(res, sbs[j]);
    }

    for (int i = 0; i < numRows; i++) { // 释放内存
        free(sbs[i]);
    }
    free(sbs);

    return res;
}

// 方案一
// 时间复杂度：O(n)
// 空间复杂度：O(n)
char* convert1(char* s, int numRows) {
    if (numRows == 1) {
        return s;
    }

    // 创建 numRows 个 StringBuilder
    char** sbs = (char**) malloc(sizeof(char*) * numRows);
    for (int i = 0; i < numRows; i++) {
        sbs[i] = (char*) malloc(sizeof(char) * (strlen(s) + 1)); // 预分配存储空间
        memset(sbs[i], '\0', sizeof(char) * (strlen(s) + 1)); // 初始化为 "\0"
    }

    int n = strlen(s), i = 0;
    while (i < n) {
        // 垂直向下
        for (int idx = 0; idx < numRows && i < n; idx++) {
            sbs[idx][strlen(sbs[idx])] = s[i];
            i++;
        }

        // 右前向上
        for (int idx = numRows - 2; idx >= 1 && i < n; idx--) {
            sbs[idx][strlen(sbs[idx])] = s[i];
            i++;
        }
    }

    char* res = (char*) malloc(sizeof(char) * (n + 1));
    memset(res, '\0', sizeof(char) * (n + 1)); // 初始化为 "\0"
    for (int j = 0; j < numRows; j++) {
        strcat(res, sbs[j]);
    }

    for (int i = 0; i < numRows; i++) { // 释放内存
        free(sbs[i]);
    }
    free(sbs);

    return res;
}